/**
  题目:
     给定一个非空二叉树，返回其最大路径和。

     本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
     
      
     
     示例 1：
     
     输入：[1,2,3]
     
            1
           / \
          2   3
     
     输出：6
     示例 2：
     
     输入：[-10,9,20,null,null,15,7]
     
        -10
        / \
       9  20
         /  \
        15   7
     
     输出：42

 
 
 
     
 
 
   思路:
      1. 递归： 理解题意
	   /**
        对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
        1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
        2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
        **/
	 
*/
 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
//需要注意的是，这个不一定会过根节点
    int maxVal=INT_MIN;
    int maxPathSum(TreeNode* root) {
        if(!root){
            return 0;
        }
        maxVal=root->val;
        calc(root);
        return maxVal; 
    }
    int calc(TreeNode*node){
        if(!node){
            return 0;
        }
        int leftVal=max( calc(node->left),0);
        int rightVal=max( calc(node->right),0);
        maxVal=max(maxVal,leftVal+rightVal+node->val);
        return max(leftVal,rightVal)+ node->val;
    }
};